package com.gorkr.dp;

import org.junit.jupiter.api.Test;

/**
 * @author gorkr
 * @date 2022/06/16 08:26
 **/
public class M583DeleteOperationForTwoStrings {

    public int minDistance(String word1, String word2) {
        int lcs = dp(word1, word2);
        return word1.length()-lcs+word2.length()-lcs;
    }

    /**
     * lcs动态规划
     * @param word1
     * @param word2
     * @return
     */
    private int dp(String word1, String word2){
        // 定义dp dp[i][j] = word1[i...]和word2[j...]的lcs
        int[][] dp = new int[word1.length()+1][word2.length()+1];
        // base case
        for (int i = 0; i < word1.length() + 1; i++) {
            dp[i][word2.length()] = 0;
        }
        for (int i = 0; i < word2.length() + 1; i++) {
            dp[word1.length()][i] = 0;
        }
        for (int i = word1.length()-1; i >=0; i--) {
            for (int j = word2.length()-1; j >=0; j--) {
                if(word1.charAt(i)==word2.charAt(j)){
                    dp[i][j] = dp[i+1][j+1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j+1]);
                }
            }
        }
        return dp[0][0];
    }

    @Test
    public void test(){
        System.out.println(minDistance("mart", "karma"));
    }

}
    